#include <bits/stdc++.h>
using namespace std;

/*
2359. 找到离给定两个节点最近的节点
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。

有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。

同时给你两个节点 node1 和 node2 。

请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。

注意 edges 可能包含环。

 

示例 1：



输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
输出：2
解释：从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。
两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。
示例 2：



输入：edges = [1,2,-1], node1 = 0, node2 = 2
输出：2
解释：节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。
两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。
 

提示：

n == edges.length
2 <= n <= 105
-1 <= edges[i] < n
edges[i] != i
0 <= node1, node2 < n
*/

// 法一
class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        // dis
        int n = edges.size();
        vector<int> dis1(n, INT_MAX);
        vector<int> dis2(n, INT_MAX);

        // 第一个点的BFS
        queue<int> q;
        q.push(node1);
        dis1[node1] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            int v = edges[u];
            if (v != -1 && dis1[v] == INT_MAX) {
                dis1[v] = dis1[u] + 1;
                q.push(v);
            }
        }

        // 第二个点 相同的BFS处理
        q.push(node2);
        dis2[node2] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            int v = edges[u];
            if (v != -1 && dis2[v] == INT_MAX) {
                dis2[v] = dis2[u] + 1;
                q.push(v);
            }
        }

        int min_max = INT_MAX;
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            if (dis1[i] != INT_MAX && dis2[i] != INT_MAX) {
                int cur_max = max(dis1[i], dis2[i]);
                if (cur_max < min_max) {
                    min_max = cur_max;
                    ans = i;
                } else if (cur_max == min_max && i < ans) {
                    ans = i;
                }
            }
        }
        return ans;
    }
};

// 法二
// 超强移动指针
class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        const int n = edges.size();
        vector<bool> visited1(n, false);  // 记录从 node1 出发访问过的节点
        vector<bool> visited2(n, false);  // 记录从 node2 出发访问过的节点
        int i = node1, j = node2;        // 初始化两个指针，分别从 node1 和 node2 开始遍历

        while (true) {
            // 如果两个指针都陷入了循环（即访问过的节点再次被访问），说明没有共同可达节点，返回 -1
            if (visited1[i] && visited2[j]) return -1;

            // 标记当前节点为已访问
            visited1[i] = true;
            visited2[j] = true;

            // 检查当前节点是否被对方访问过：
            // 如果 node1 的当前节点 i 被 node2 访问过，或者 node2 的当前节点 j 被 node1 访问过，
            // 说明找到了共同可达节点，返回其中编号较小的那个
            if (visited2[i]) return visited1[j] ? min(i, j) : i;
            if (visited1[j]) return visited2[i] ? min(i, j) : j;

            // 如果两个指针都无法继续移动（即都到达了出边为 -1 的节点），说明没有共同可达节点，返回 -1
            if (edges[i] == -1 && edges[j] == -1) return -1;

            // 移动指针 i：如果当前节点 i 的出边不为 -1 且下一个节点未被访问过，则移动到下一个节点
            if (edges[i] != -1 && !visited1[edges[i]]) {
                i = edges[i];
            }

            // 移动指针 j：如果当前节点 j 的出边不为 -1 且下一个节点未被访问过，则移动到下一个节点
            if (edges[j] != -1 && !visited2[edges[j]]) {
                j = edges[j];
            }
        }

        return -1;  // 这里理论上不会执行到，因为 while(true) 循环内部已经处理了所有情况
    }
};